package com.example.demo.leetcode;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;

/**
 * 链接: <a href="https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/?envType=daily-question&envId=2024-02-23">https://leetcode.cn/problems/kth-largest-sum-in-a-binary-tree/description/?envType=daily-question&envId=2024-02-23</a>
 *
 * @author WangYX
 * @version 1.0.0
 * @date 2024/02/23 11:28
 */
public class _2583_二叉树中的第K大层和 {


    public static void main(String[] args) {
        TreeNode root = new TreeNode(5,
                new TreeNode(8,
                        new TreeNode(2,
                                new TreeNode(4, null, null),
                                new TreeNode(6, null, null)),
                        new TreeNode(1, null, null)),
                new TreeNode(9,
                        new TreeNode(3, null, null),
                        new TreeNode(7, null, null))
        );

        TreeNode root1 = new TreeNode(1, new TreeNode(2, new TreeNode(3, null, null), null), null);


        long l = kthLargestLevelSum(root1, 1);
        System.out.println(l);
    }


    public static long kthLargestLevelSum(TreeNode root, int k) {
        if (root == null) {
            return -1;
        }
        List<Long> sumArr = new ArrayList<>();
        ArrayDeque<TreeNode> deque = new ArrayDeque<>();
        deque.offer(root);
        while (!deque.isEmpty()) {
            int size = deque.size();
            long sum = 0;
            for (int i = 0; i < size; i++) {
                TreeNode poll = deque.poll();
                sum += poll.val;
                if (poll.left != null) {
                    deque.offer(poll.left);
                }
                if (poll.right != null) {
                    deque.offer(poll.right);
                }
            }
            sumArr.add(sum);
        }
        if (k <= sumArr.size()) {
            sumArr.sort(Long::compareTo);
            return sumArr.get(k);
        }
        return -1;
    }
}
